The relatively rapid speed at which content addressable memories (CAMs) can compare multiple entries to an applied search key value, has resulted in CAMs enjoying widespread use in higher speed applications, such as network packet processing.
Conventional CAMs may include binary CAMs and ternary CAMs. Binary CAMs typically include entries that can each store a data value having a number of data bits. In most cases, a match indication can be generated when all bits of a search key match all the bits of an entry. Thus, in a typical binary CAM, bits of an entry may have a value of 0 or 1. A corresponding search key (i.e., comparand) value is said to match its corresponding entry when it is exactly the same.
CAMs may also include ternary CAMs. Ternary CAMs may typically include entries having data bits that can be masked from a compare operation. Thus, in a typical ternary CAM, bits of an entry can be conceptualized as having a value of 0, 1 or “X”. A corresponding search key bit value is said to match its corresponding entry bit when it is either the same, or when the entry bit has the X (“don't care” or masked) value.
Recently, various packet processing operations have given rise to the need for range matching operations. In a range matching operation, a portion (or all) of a search key value can be examined to determine if it falls within a range, as opposed to simply matching an entry value. One particular application that can employ range matching can be access control lists (ACL). An ACL may present a set of rules that can limit access (e.g., forwarding of packets) to only those packets having fields failing within a particular range.
Conventionally, CAMs have been utilized to express rules to provide range rule matching functions. A first conventional range rule matching arrangement is represented in FIGS. 20A, 20B and 21. FIGS. 20A and 20B illustrate how a range can be encoded according to common prefix values.
FIG. 20A shows how three ranges R<2, 2≦R≦3 and R>3 are encoded into four entries over a space of 0-15 (0000-1111 binary). As shown, those values lower than the range 2-3 can be encoded by utilizing an entry value of 000X, which has a common prefix of “000”. The range itself, encodes into an entry value of 001×, which has a common prefix of “000”. The range 2≦R≦3 encodes into one entry “001X”. Finally, those values in the last range R>3 encode into two entries, one having a common prefix of “01” the other having a common prefix of “1”.
In this way, a range can be “enumerated” by prefixes values that contain the range, or portions of the range.
One skilled in the art would recognize that such worst case result for a conventional prefix enumeration approach can be generalized as follows. For a range space defined by a W bits, the worst case number of rules (i.e., entries) to define a range ends up being 2W−2.
A drawback to the conventional arrangement is represented by FIG. 20B. The conventional approach of enumerating prefix can provide relatively compact results (a small number of entries) only when a range falls on convenient boundaries. As shown by FIG. 20B, a range of 7-10 in a space 0-15 encodes into 3 entries. Such a result represents a worst case result, as there is a prefix greater than one on each side of the range.
FIG. 21 shows a CAM device that may incorporate the range matching arrangement of FIGS. 20A and 20B. As shown by FIG. 21, a CAM device 2100 can be a conventional ternary CAM device that applies a search key value that includes W bits to ternary CAM entries 2102-1 to 2102-n. Each CAM entry (2102-1 to 2102-n) can include a corresponding W bits for storing a range rule. It is understood that all bits of a search key value can carry range bit values, or only a portion thereof (e.g., the search key has one or more groups of bits for comparison to one or more ranges).
While a conventional approach like that of FIGS. 20A, 20B and 21 may result in an undesirably large number of entries when encoding certain range values, the approach does have a number of advantages. First, little (or no) additional hardware may be needed accommodate range matching. Second, updating the CAM device can be accomplished relatively quickly. If new range information is needed, provided empty entries are available, new values are written into the CAM (assuming no additional priority for such entries is required).
A second conventional range rule matching arrangement is represented in FIGS. 22A and 22B and 23. FIGS. 22A and 22B illustrate how a range portion of a rule can be uniquely encoded utilizing range preclassification. In a conventional range preclassification approach, entire ranges are encoded into unique values.
FIGS. 22A and 22B show how preclassification can encode the same range values as those shown in FIGS. 20A and 20B. As shown by FIGS. 22A and 22B, preclassification can encode any range into one value ENC regardless of where the range falls along bit boundaries.
In this way, a range rule can be mapped to a unique entry value. One skilled in the art would recognize that conventional preclassification can greatly reduce the number of rules (essentially one entry per range rule).
However, conventional preclassification approaches can have drawbacks. First, preclassification can require knowledge of an entire range mapping database, in order to ensure unique values are provided for each range. That is, before any new range is added, an entire existing database is checked to ensure that the encoded value will be unique to the range.
FIG. 23 shows a CAM device that may incorporate the range rule matching arrangement of FIGS. 22A and 22B. As shown by FIG. 23, a CAM device 2300 can be a conventional ternary or binary CAM device that applies a search key value of W bits to CAM entries 2302-1 to 2302-n, each of which includes a corresponding W bits for storing a range rule.
In the event preclassification is performed “on-board” the device, the CAM device 2300 will have to include preclassification hardware 2304. This may undesirably increase the size and complexity of the device. If preclassification is performed outside of the CAM device 2300, a processor or the like, along with accompanying routines would be necessary to preprocess range values prior to application to the CAM device 2300.
Referring now to FIG. 24, one example of a range rule search key is shown to illustrate how a search key can require both standard bit matching (ternary matching) as well as range matching. The search key of FIG. 24 includes five search fields (FIELD1 to FIELD5). Search fields FIELD1, FIELD3 and FIELD4 are ternary match fields. Thus, these fields can be compared on a bit wise basis to arrive at a match result. However, search fields FIELD2 and FIELD5 are range match fields. Thus, such fields are examined to determine if they fall within a given range in order to arrive at a match result.
The above example shows how range rule matching can require numerous entries when expressed within a CAM device.
In light of the above, it would be desirable to arrive at some way of providing range rule matching capabilities that can result in a smaller number of rules than conventional prefix enumeration approaches.
At the same time, it would also be desirable to arrive at some way of providing range rule matching capabilities that provides faster and/or easier updating of rules than conventional preclassification approaches.